# -*- coding: utf-8 -*- 
# @project : 《剑指offer》
# @Author : created by bensonrachel on 2021/6/10
# @File : 机器人的运动范围BFS.py
class Solution(object):
    def movingCount(self, k, rows, cols):#BFS 用队列实现，先出一个，然后根据出的这一个来入队一批，再出一个，再根据。。以此类推
        """
        :type threshold: int
        :type rows: int
        :type cols: int
        :rtype: int
        """
        def is_val(a,b):
            x = a
            y = b
            if(a>=10): x = int(str(a)[0])+int(str(a)[1])
            if(b>=10): y = int(str(b)[0])+int(str(b)[1])
            return (x+y<=k)
        list = []
        list.append((0,0))
        dict = {}
        dict[(0,0)] = 1#用字典，key为元组类型，value 为 int类型来保存走过的坐标(x,y)。
        tag = 0
        if(cols == 0 or rows ==0):return 0
        while(list):#直到list为空，则不用再输出
            tup = list[0]
            list = list[1:]
            tag += 1
            a = (tup[0],tup[1]+1)#四个方位
            b = (tup[0],tup[1]-1)
            c = (tup[0]+1,tup[1])
            d = (tup[0]-1,tup[1])
            list1 = [a,b,c,d]
            for i in list1:
                if(0 <= i[0] < rows and 0<= i[1] < cols):
                    if(is_val(i[0],i[1]) and i not in dict):
                        dict[i] = 1
                        list.append(i)
        return tag